
/*
Description:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?

*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
	bool search(vector<int>& nums, int target) {

		return true;
	}
};

int _searchInRoatedSortedArray2()
{
	vector<int> nums{ 4,5,6,7,8,1,2,3 }; // { 4, 5, 6, 7, 0, 1, 2 };
	int target = 8;

	Solution solu;
	int pos;

	pos = solu.search(nums, target);

	cout << "nums:" << endl;
	for (auto v : nums) cout << v << " ";
	cout << endl;
	cout << "target: " << target << endl;
	cout << "found: " << pos << endl;
	return 0;
}